Recently, distributed hash table (DHT) overlay networks have been used to solve the problem of data placement and retrieval in large scale, Internet-sized storage systems. These systems generally include distributed network systems implemented, for example, using peer-to-peer (P2P) networks for storing vast amounts of data. The overlay networks are logical representations built on top of the underlying physical networks, which provide, among other types of functionality, data placement, information retrieval, routing, etc. Some examples of DHT overlay networks include content-addressable-network (CAN), PASTRY, and CHORD.
DHT overlay networks attempt to guarantee the location of a data item and through use of a hash table provide a means for retrieving data from their guaranteed locations. DHT overlay networks, although having good data storage and retrieval qualities, generally do not handle partitioning well. For example, if a DHT network is partitioned into two halves, a node may not know that the data it is interested in is actually available in another node in the same half, because the DHT routing algorithm requires the first node to go through a node in the other half before locating the node storing the data. This may result in increased network traffic and latencies.